home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-ietf-pppext-compression-00.txt < prev    next >
Text File  |  1993-10-21  |  32KB  |  1,043 lines
  1.  
  2. Network Working Group                                             D Rand
  3. Internet Draft                                                    Novell
  4. Expires in six months                                       October 1993
  5.  
  6.  
  7.                The PPP Compression Control Protocol (CCP)
  8.                   draft-ieft-pppext-compression-00.txt
  9.  
  10.  
  11.  
  12. Status of this Memo
  13.  
  14.    This document is the product of the Point-to-Point Protocol Working
  15.    Group of the Internet Engineering Task Force (IETF).  Comments should
  16.    be submitted to the ietf-ppp@ucdavis.edu mailing list.
  17.  
  18.    Distribution of this memo is unlimited.
  19.  
  20.    This document is an Internet Draft.  Internet Drafts are working
  21.    documents of the Internet Engineering Task Force (IETF), its Areas,
  22.    and its Working Groups.  Note that other groups may also distribute
  23.    working documents as Internet Drafts.
  24.  
  25.    Internet Drafts are draft documents valid for a maximum of six
  26.    months.  Internet Drafts may be updated, replaced, or obsoleted by
  27.    other documents at any time.  It is not appropriate to use Internet
  28.    Drafts as reference material or to cite them other than as a
  29.    ``working draft'' or ``work in progress.''
  30.  
  31.    Please check the 1id-abstracts.txt listing contained in the
  32.    internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net,
  33.    nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the
  34.    current status of any Internet Draft.
  35.  
  36. Abstract
  37.  
  38.    The Point-to-Point Protocol (PPP) [1] provides a standard method of
  39.    encapsulating multiple protocol datagrams over point-to-point links.
  40.    PPP also defines an extensible Link Control Protocol.
  41.  
  42.    This document defines a method for negotiating data compression over
  43.    PPP links, and describes the use of several such data compression
  44.    protocols.
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53. Dave Rand                expires in six months                  [Page i]
  54. DRAFT                       PPP Compression                 October 1993
  55.  
  56.  
  57. 1.  Introduction
  58.  
  59.    PPP has three main components:
  60.  
  61.       1. A method for encapsulating datagrams over serial links.
  62.  
  63.       2. A Link Control Protocol (LCP) for establishing, configuring,
  64.          and testing the data-link connection.
  65.  
  66.       3. A family of Network Control Protocols (NCPs) for establishing
  67.          and configuring different network-layer protocols.
  68.  
  69.    In order to establish communications over a point-to-point link, each
  70.    end of the PPP link must first send LCP packets to configure and test
  71.    the data link.  After the link has been established and optional
  72.    facilities have been negotiated as needed by the LCP, PPP must send
  73.    NCP packets to choose and configure one or more network-layer
  74.    protocols.  Once each of the chosen network-layer protocols has been
  75.    configured, datagrams from each network-layer protocol can be sent
  76.    over the link.
  77.  
  78.    The link will remain configured for communications until explicit LCP
  79.    or NCP packets close the link down, or until some external event
  80.    occurs (an inactivity timer expires or network administrator
  81.    intervention).
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108. Dave Rand                expires in six months                  [Page 1]
  109. DRAFT                       PPP Compression                 October 1993
  110.  
  111.  
  112. 2.  A PPP Control Protocol (NCP) for Compression
  113.  
  114.    The Compression Control Protocol (CCP) is responsible for
  115.    configuring, enabling, and disabling data compression algorithms on
  116.    both ends of the point-to-point link.  It is also used to signal a
  117.    failure of the compression/decompression mechanism in a reliable
  118.    manner.  CCP uses the same packet exchange machanism as the Link
  119.    Control Protocol (LCP).  CCP packets may not be exchanged until PPP
  120.    has reached the Network-Layer Protocol phase.  CCP packets received
  121.    before this phase is reached should be silently discarded.
  122.  
  123.    The Compression Control Protocol is exactly the same as the Link
  124.    Control Protocol [1] with the following exceptions:
  125.  
  126.    Data Link Layer Protocol Field
  127.  
  128.       Exactly one CCP packet is encapsulated in the Information field of
  129.       PPP Data Link Layer frames where the Protocol field indicates type
  130.       hex <TBD> (0xFD) (Compression Control Protocol).
  131.  
  132.    Code field
  133.  
  134.       Only Codes 1 through 7 (Configure-Request, Configure-Ack,
  135.       Configure-Nak, Configure-Reject, Terminate-Request, Terminate-Ack
  136.       and Code-Reject) are used.  Other Codes should be treated as
  137.       unrecognized and should result in Code-Rejects.
  138.  
  139.    Timeouts
  140.  
  141.       CCP packets may not be exchanged until PPP has reached the
  142.       Network-Layer Protocol phase.  An implementation should be
  143.       prepared to wait for Authentication and Link Quality Determination
  144.       to finish before timing out waiting for a Configure-Ack or other
  145.       response.  It is suggested that an implementation give up only
  146.       after user intervention or a configurable amount of time.
  147.  
  148.    Configuration Option Types
  149.  
  150.       CCP has a distinct set of Configuration Options, which are defined
  151.       below.
  152.  
  153. 2.1.  Sending Compressed Datagrams
  154.  
  155.    Before any compressed packets may be communicated, PPP must reach the
  156.    Network-Layer Protocol phase, and the Compression Control Protocol
  157.    must reach the Opened state.
  158.  
  159.    One or more compressed packets are encapsulated in the Information
  160.  
  161.  
  162.  
  163. Dave Rand                expires in six months                  [Page 2]
  164. DRAFT                       PPP Compression                 October 1993
  165.  
  166.  
  167.    field of PPP Data Link Layer frames.  Each of the compression types
  168.    may use a different mechanism to indicate the inclusion of more than
  169.    one uncompressed frame in a single PPP Data Link Layer frame.  The
  170.    Protocol Identifier of the compressed datagram indicates that the
  171.    frame is compressed, but not the algorithm with which it was
  172.    compressed.  Only one algorithm may be in use at time, and that is
  173.    negotiated prior to the first compressed frame being transmitted.
  174.  
  175.    The maximum length of a compressed packet transmitted over a PPP link
  176.    is the same as the maximum length of the Information field of a PPP
  177.    data link layer frame.  Larger datagrams (presumably the result of
  178.    the compression algorithm increasing the size of the message in some
  179.    cases) may be sent uncompressed, using its standard form, or may be
  180.    sent in multiple datagrams, if the compression algorithm supports it.
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218. Dave Rand                expires in six months                  [Page 3]
  219. DRAFT                       PPP Compression                 October 1993
  220.  
  221.  
  222. 3.  CCP Configuration Options
  223.  
  224. CCP Configuration Options allow negotiatiation of compression algorithms
  225. and their parameters.  CCP uses the same Configuration Option format
  226. defined for LCP [1], with a separate set of Options.
  227.  
  228. Configuration Options, in this protocol, indicate algorithms that the
  229. receiver is willing or able to use to decompress data sent by the
  230. sender.  As a result, it is to be expected that systems will offer to
  231. accept several differing sets of algorithms, and negotiate down to one
  232. that will indeed be used.
  233.  
  234. There is the possibility of not being able to agree on a compression
  235. algorithm.  In that case, no compression will be used, and the link will
  236. come up without compression.  If LAPB has been separately negotiated,
  237. then LAPB will be used (unless it is re-negotiated off).
  238.  
  239. We expect many vendors to want to use proprietary compression
  240. algorithms, and have made a mechanism available to negotiate these
  241. without encumbering the Internet Assigned Number Authority with
  242. proprietary number requests.
  243.  
  244. If any of the protocols are not recognized, a Configure-Reject must be
  245. sent for all protocols that are not recognized.  If any of the protocols
  246. are recognized, but not acceptable due to local options in the request,
  247. a Configure-Nak should be sent with the local options modified
  248. appropriately.  A new Configure-Request may then be sent with the
  249. options adjusted as specified in the Configure-Nak.
  250.  
  251. Compression algorithm options are listed in the order of their
  252. desireableness to the receiver.  If the sender chooses to implement only
  253. one compression algorithm on the line (for example), he first determines
  254. what subset of the receiver's algorithms he can use, and among them
  255. chooses the most desireable - the first option listed.
  256.  
  257. The most up-to-date values of the CCP Option Type field are specified in
  258. the most recent "Assigned Numbers" RFC [6].  Current values are assigned
  259. as follows:
  260.  
  261.    CCP Option      Meaning
  262.    1       Compression type negotiation (common)
  263.    2       Compression type negotiation (OUI/proprietary)
  264.  
  265.  
  266.  
  267.  
  268.  
  269.  
  270.  
  271.  
  272.  
  273. Dave Rand                expires in six months                  [Page 4]
  274. DRAFT                       PPP Compression                 October 1993
  275.  
  276.  
  277. 3.1.  Compression Type Negotiation Option (common)
  278.  
  279.    Description
  280.  
  281.       This Configuration Option provides a way to negotiate the use of a
  282.       standard compression algorithm.  As of this writing, several
  283.       compression algorithms are specified (see appendix). By default,
  284.       compression is not enabled.
  285.  
  286.  
  287.     0                   1                   2                   3
  288.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  289.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  290.    |     Type      |          Length               | Compression   |
  291.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  292.    |  Length       | options...
  293.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  294.  
  295.    Type
  296.  
  297.       1
  298.  
  299.    Length
  300.  
  301.       >= 3
  302.  
  303.    Compression Types
  304.  
  305.       The compression types field lists the common compression
  306.       algorithms that the are available.  They must be listed in the
  307.       order of desirability for this particular link.  Each compression
  308.       type is followed with a length, which may be 0.  The length
  309.       indicates the number of octets of compression-specific negotiation
  310.       information, which may include items such as dictionary size,
  311.       maximum string length and number of dictionaries.
  312.  
  313.       The receiver will process the compression types field from left to
  314.       right, selecting the first protocol that matches the receiver's
  315.       capability. This protocol will be Configure-ACKed.  If a protocol
  316.       is understood, but some (or all) of the compression negotiation
  317.       options are not acceptable, these may be modified and sent back in
  318.       a Configure-Nak.  If any of the protocols are not understood, a
  319.       Configure-Reject must be sent back including all protocols not
  320.       understood.
  321.  
  322.       Implementation of any particular compression algorithm IS NOT
  323.       guaranteed.  If all protocols the sender implements are
  324.       Configure-Rejected by the receiver, then no compression is
  325.  
  326.  
  327.  
  328. Dave Rand                expires in six months                  [Page 5]
  329. DRAFT                       PPP Compression                 October 1993
  330.  
  331.  
  332.       enabled.
  333.  
  334.    Default
  335.  
  336.       No compression protocol enabled.
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345.  
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353.  
  354.  
  355.  
  356.  
  357.  
  358.  
  359.  
  360.  
  361.  
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369.  
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382.  
  383. Dave Rand                expires in six months                  [Page 6]
  384. DRAFT                       PPP Compression                 October 1993
  385.  
  386.  
  387. 3.2.  Compression Type Negotiation Option (OUI/Proprietary)
  388.  
  389.    Description
  390.  
  391.       This Configuration Option provides a way to negotiate the use of a
  392.       proprietary compression protocol.  By default, such compression is
  393.       not enabled.  Since the first matching compression will be used,
  394.       it is recommended that any known OUI compression options be
  395.       transmitted first, before the common options are used.  Before
  396.       accepting this option, the implementation must verify that the
  397.       Organizationally Unique Identifier identifies a proprietary
  398.       algorithm that the implementation can decompress, and that any
  399.       vendor specific negotiation options are fully understood.  If no
  400.       OUIs are supported by an implementation, a Configure-Reject may be
  401.       sent back for any type 2 Compression Type Negotiation Option.
  402.  
  403.    A summary of the Proprietary Compression Algorithm Configuration
  404.    Option format is shown below.  The fields are transmitted from left
  405.    to right.
  406.  
  407.     0                   1                   2                   3
  408.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  409.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  410.    |     Type      |          Length               | OUI MS octet  |
  411.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  412.    |     OUI remaining octects     |  Length       | options...
  413.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  414.  
  415.    Type
  416.  
  417.       2
  418.  
  419.    Length
  420.  
  421.       >= 3
  422.  
  423.    IEEE OUI
  424.  
  425.       The vendor's IEEE Organizationally Unique Identifier (OUI), which
  426.       is the most significant three octets of an Ethernet Physical
  427.       Address, assigned to the vendor by IEEE 802.  This identifies the
  428.       option as being proprietary to the indicated vendor.
  429.  
  430.       Multiple proprietary compression types may be offered, each with a
  431.       different OUI, by sending them out after a REJect for any previous
  432.       OUI has been received by the sender.
  433.  
  434.       Multiple vendor-specific proprietary compression types may be
  435.  
  436.  
  437.  
  438. Dave Rand                expires in six months                  [Page 7]
  439. DRAFT                       PPP Compression                 October 1993
  440.  
  441.  
  442.       implemented by the option field, which may contain algorithm
  443.       selection information, negotiated options such as dictionary size,
  444.       or any other information required.
  445.  
  446.       Any unrecognized proprietary compression configure requests MUST
  447.       have a Configure-Reject sent back.
  448.  
  449.    Length
  450.  
  451.       The Length field specifies the number of octects of OUI-specific
  452.       negotiation information, in free format.  It may be followed by 0
  453.       to 255 octets of negotiation information.
  454.  
  455.  
  456.    options
  457.       The options field is zero or more octets and contains additional
  458.       data as determined by the vendor's compression protocol.
  459.  
  460.    Default
  461.  
  462.       No proprietary compression protocol enabled.
  463.  
  464.  
  465.  
  466.  
  467.  
  468.  
  469.  
  470.  
  471.  
  472.  
  473.  
  474.  
  475.  
  476.  
  477.  
  478.  
  479.  
  480.  
  481.  
  482.  
  483.  
  484.  
  485.  
  486.  
  487.  
  488.  
  489.  
  490.  
  491.  
  492.  
  493. Dave Rand                expires in six months                  [Page 8]
  494. DRAFT                       PPP Compression                 October 1993
  495.  
  496.  
  497. A.  Common compression number identification
  498.  
  499.    The following numbers for common compression option use have been
  500.    defined.
  501.  
  502.       Compression ID  Algorithm specified
  503.       1       Predictor type 1
  504.       2       Predictor type 2
  505.       3       Puddle Jumper
  506.       16      Hewlett-Packard PPC
  507.       17      Stac Electronics LZS
  508.       18      Microsoft PPC
  509.       19      Gandalf FZA
  510.  
  511.       IDs 4-15 are reserved for other freely-available implementations
  512.       of compression algorithms.
  513.  
  514.  
  515.  
  516.  
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523.  
  524.  
  525.  
  526.  
  527.  
  528.  
  529.  
  530.  
  531.  
  532.  
  533.  
  534.  
  535.  
  536.  
  537.  
  538.  
  539.  
  540.  
  541.  
  542.  
  543.  
  544.  
  545.  
  546.  
  547.  
  548. Dave Rand                expires in six months                  [Page 9]
  549. DRAFT                       PPP Compression                 October 1993
  550.  
  551.  
  552. B.  Common compression algorithm definitions
  553.  
  554.    A compression algorithm that is available without license fees is the
  555.    predictor algorithm, defined below.  Note that although care has been
  556.    taken to ensure that the following code does not infringe any
  557.    patents, there is no assurance that it is not covered by a patent.
  558.    Use the following code at your own risk.
  559.  
  560.    B.1.  Predictor algorithm
  561.  
  562.       Predictor works by filling a guess table with values, based on the
  563.       hash of the previous characters seen. Since we are either emitting
  564.       the source data, or depending on the guess table, we add a flag
  565.       bit for every byte of input, telling the decompressor if it should
  566.       retrieve the byte from the compressed data stream, or the guess
  567.       table. Blocking the input into groups of 8 characters means that
  568.       we don't have to bit-insert the compressed output - a flag byte
  569.       preceeds every 8 bytes of compressed data. Each bit of the flag
  570.       byte corresponds to one byte of reconstructed data.
  571.  
  572.       Take the source file:
  573.  
  574.       000000    4141 4141 4141 410a  4141 4141 4141 410a    AAAAAAA.AAAAAAA.
  575.       000010    4141 4141 4141 410a  4141 4141 4141 410a    AAAAAAA.AAAAAAA.
  576.       000020    4142 4142 4142 410a  4241 4241 4241 420a    ABABABA.BABABAB.
  577.       000030    7878 7878 7878 780a                         xxxxxxx.
  578.  
  579.       Compressing the above data yields the following:
  580.  
  581.       000000    6041 4141 4141 0a60  4141 4141 410a 6f41    `AAAAA.`AAAAA.oA
  582.       000010    0a6f 410a 4142 4142  4142 0a60 4241 4241    .oA.ABABAB.`BABA
  583.       000020    420a 6078 7878 7878  0a                     B.`xxxxx.
  584.  
  585.       Reading the above data says:
  586.       flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
  587.            Reconstructed data is:    0 1 2 3 4 5 6 7
  588.               File:                  A A A A A
  589.               Guess table:                     A A
  590.       flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
  591.            Reconstructed data is:    0 1 2 3 4 5 6 7
  592.               File:                  A A A A A
  593.               Guess table:                     A A
  594.       flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6.
  595.            Reconstructed data is:    0 1 2 3 4 5 6 7
  596.               File:                          A
  597.               Guess table:           A A A A   A A
  598.       flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6.
  599.            Reconstructed data is:    0 1 2 3 4 5 6 7
  600.  
  601.  
  602.  
  603. Dave Rand                expires in six months                 [Page 10]
  604. DRAFT                       PPP Compression                 October 1993
  605.  
  606.  
  607.               File:                          A
  608.               Guess table:           A A A A   A A
  609.       flag = 0x41 - 2 bytes in this block were guessed correctly, 0 and 6.
  610.            Reconstructed data is:    0 1 2 3 4 5 6 7
  611.               File:                    B A B A B
  612.               Guess table:           A           A
  613.       flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
  614.            Reconstructed data is:    0 1 2 3 4 5 6 7
  615.               File:                  B A B A B
  616.               Guess table:                     A B
  617.       flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6
  618.            Reconstructed data is:    0 1 2 3 4 5 6 7
  619.               File:                  x x x x x
  620.               Guess table:                     x x
  621.  
  622.       And now, on to the source - note that it has been modified to work
  623.       with a split block. If your data stream can't be split within a
  624.       block (eg, compressing packets), then the code dealing with
  625.       "final", and the memcpy are not required.  You can detect this
  626.       situation (or errors, for that matter) by observing that the flag
  627.       byte indicates that more data is required from the compressed data
  628.       stream, but you are out of data (len in decompress is <= 0). It
  629.       *is* ok if len == 0, and flags indicate guess table usage.
  630.  
  631.       #include <stdio.h>
  632.       #ifdef __STDC__
  633.       #include <stdlib.h>
  634.       #endif
  635.       #include <string.h>
  636.       /*
  637.        * pred.c -- Test program for Dave Rand's rendition of the
  638.        * predictor algorithm
  639.        * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson)
  640.        * Updated by: Carsten Bormann <cabo@cs.tu-berlin.de>
  641.        * Original  : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com>
  642.        */
  643.  
  644.       /* The following hash code is the heart of the algorithm:
  645.        * It builds a sliding hash sum of the previous 3-and-a-bit characters
  646.        * which will be used to index the guess table.
  647.        * A better hash function would result in additional compression,
  648.        * at the expense of time.
  649.        */
  650.       #define HASH(x) Hash = (Hash << 4) ^ (x)
  651.  
  652.       static unsigned short int Hash;
  653.       static unsigned char GuessTable[65536];
  654.  
  655.  
  656.  
  657.  
  658. Dave Rand                expires in six months                 [Page 11]
  659. DRAFT                       PPP Compression                 October 1993
  660.  
  661.  
  662.       static int
  663.       compress(source, dest, len)
  664.       unsigned char *source, *dest;
  665.       int len;
  666.       {
  667.           int i, bitmask;
  668.           unsigned char *flagdest, flags, *orgdest;
  669.  
  670.           orgdest = dest;
  671.           while (len) {
  672.               flagdest = dest++; flags = 0;   /* All guess wrong initially */
  673.               for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) {
  674.                   if (GuessTable[Hash] == *source) {
  675.                       flags |= bitmask;       /* Guess was right - don't output */
  676.                   } else {
  677.                       GuessTable[Hash] = *source;
  678.                       *dest++ = *source;      /* Guess wrong, output char */
  679.                   }
  680.                   HASH(*source++);len--;
  681.               }
  682.               *flagdest = flags;
  683.           }
  684.           return(dest - orgdest);
  685.       }
  686.  
  687.       static int
  688.       decompress(source, dest, lenp, final)
  689.       unsigned char *source, *dest;
  690.       int *lenp, final;
  691.       {
  692.           int i, bitmask;
  693.           unsigned char flags, *orgdest;
  694.           int len = *lenp;
  695.  
  696.           orgdest = dest;
  697.           while (len >= 9) {
  698.               flags = *source++;
  699.               for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
  700.                   if (flags & bitmask) {
  701.                       *dest = GuessTable[Hash];       /* Guess correct */
  702.                   } else {
  703.                       GuessTable[Hash] = *source;     /* Guess wrong */
  704.                       *dest = *source++;              /* Read from source */
  705.                       len--;
  706.                   }
  707.                   HASH(*dest++);
  708.               }
  709.               len--;
  710.  
  711.  
  712.  
  713. Dave Rand                expires in six months                 [Page 12]
  714. DRAFT                       PPP Compression                 October 1993
  715.  
  716.  
  717.           }
  718.           while (final && len) {
  719.               flags = *source++;
  720.               len--;
  721.               for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
  722.                   if (flags & bitmask) {
  723.                       *dest = GuessTable[Hash];       /* Guess correct */
  724.                   } else {
  725.                       if (!len)
  726.                           break;      /* we seem to be really done -- cabo */
  727.                       GuessTable[Hash] = *source;     /* Guess wrong */
  728.                       *dest = *source++;              /* Read from source */
  729.                       len--;
  730.                   }
  731.                   HASH(*dest++);
  732.               }
  733.           }
  734.           *lenp = len;
  735.           return(dest - orgdest);
  736.       }
  737.  
  738.       #define SIZ1 8192
  739.  
  740.       static void
  741.       compress_file(f) FILE *f; {
  742.           char bufp[SIZ1];
  743.           char bufc[SIZ1/8*9+9];
  744.           int len1, len2;
  745.           while ((len1 = fread(bufp, 1, SIZ1, f)) > 0) {
  746.               len2 = compress((unsigned char *)bufp, (unsigned char *)bufc, len1);
  747.               (void) fwrite(bufc, 1, len2, stdout);
  748.           }
  749.       }
  750.  
  751.       static void
  752.       decompress_file(f) FILE *f; {
  753.           char bufp[SIZ1+9];
  754.           char bufc[SIZ1*9+9];
  755.           int len1, len2, len3;
  756.  
  757.           len1 = 0;
  758.           while ((len3 = fread(bufp+len1, 1, SIZ1, f)) > 0) {
  759.               len1 += len3;
  760.               len3 = len1;
  761.               len2 = decompress((unsigned char *)bufp, (unsigned char *)bufc, &len1, 0);
  762.               (void) fwrite(bufc, 1, len2, stdout);
  763.               (void) memcpy(bufp, bufp+len3-len1, len1);
  764.           }
  765.  
  766.  
  767.  
  768. Dave Rand                expires in six months                 [Page 13]
  769. DRAFT                       PPP Compression                 October 1993
  770.  
  771.  
  772.           len2 = decompress((unsigned char *)bufp, (unsigned char *)bufc, &len1, 1);
  773.           (void) fwrite(bufc, 1, len2, stdout);
  774.       }
  775.  
  776.       int
  777.       main(ac, av)
  778.           int ac;
  779.           char** av;
  780.       {
  781.           char **p = av+1;
  782.           int dflag = 0;
  783.  
  784.           for (; --ac > 0; p++) {
  785.               if (!strcmp(*p, "-d"))
  786.                   dflag = 1;
  787.               else if (!strcmp(*p, "-"))
  788.                   (dflag?decompress_file:compress_file)(stdin);
  789.               else {
  790.                   FILE *f = fopen(*p, "r");
  791.                   if (!f) {
  792.                       perror(*p);
  793.                       exit(1);
  794.                   }
  795.                   (dflag?decompress_file:compress_file)(f);
  796.                   (void) fclose(f);
  797.               }
  798.           }
  799.           return(0);
  800.       }
  801.  
  802.    B.2.  Encapsultation for Predictor type 1
  803.       The correct encapsulation for type 1 compression is the protocol
  804.       type, 1 bit indicating if the data is compressed or not, 15 bits
  805.       of the uncompressed data length in octets, compressed data, and
  806.       uncompressed CRC-16 of the two octets of unsigned length in
  807.       network byte order, followed by the original, uncompressed data
  808.       packet.
  809.  
  810.        0                   1
  811.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
  812.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  813.       | CCP Protocol Identifier       |
  814.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  815.       |*| Uncompressed length (octets)|   * is compressed flag
  816.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   1 means data is compressed
  817.       | Compressed data...            |   0 means data is not compressed
  818.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  819.       | CRC - 16                      |
  820.  
  821.  
  822.  
  823. Dave Rand                expires in six months                 [Page 14]
  824. DRAFT                       PPP Compression                 October 1993
  825.  
  826.  
  827.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  828.  
  829.       It is not required that any of the fields land on an even word
  830.       boundary - the compressed data may be of any length.  If during
  831.       the decode procedure, the CRC-16 does not match the decoded frame,
  832.       it means that the compress or decompress process has become
  833.       desyncronized.  This will happen as a result of a frame being lost
  834.       in transit if LAPB is not used.  In this case, a new configure-
  835.       request must be sent, and the CCP will drop out of the open state.
  836.       Upon receipt of the configure-ack, the predictor tables are
  837.       cleared to zero, and compression can be resumed without data loss.
  838.  
  839.    B.3.  Encapsultation for Predictor type 2
  840.       The correct encapsulation for type 2 compression is the protocol
  841.       type, followed by the data stream.  Within the data stream is the
  842.       current frame length (uncompressed), compressed data, and
  843.       uncompressed CRC-16 of the two octets of unsigned length in
  844.       network byte order, followed by the original, uncompressed data.
  845.       The data stream may be broken at any convenient place for
  846.       encapsulation purposes.  With type 2 encapsulation, LAPB is almost
  847.       essential for correct delivery.
  848.  
  849.        0                   1
  850.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
  851.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  852.       | CCP Protocol Identifier       |
  853.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  854.       |*| Uncompressed length (octets)|   * is compressed flag
  855.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   1 means data is compressed
  856.       | Compressed data...            |   0 means data is not compressed
  857.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  858.       | CRC-16                        |
  859.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  860.       |*| Uncompressed length (octets)|   * is compressed flag
  861.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  862.                ...
  863.  
  864.       It is not required that any field land on an even word boundary -
  865.       the compressed data may be of any length.  If during the decode
  866.       procedure, the CRC-16 does not match the decoded frame, it means
  867.       that the compress or decompress process has become desyncronized.
  868.       This will happen as a result of a frame being lost in transit if
  869.       LAPB is not used.  In this case, a new configure-request must be
  870.       sent, and the CCP will drop out of the open state.  Upon receipt
  871.       of the configure-ack, the predictor tables are cleared to zero,
  872.       and compression can be resumed without data loss.
  873.  
  874.  
  875.  
  876.  
  877.  
  878. Dave Rand                expires in six months                 [Page 15]
  879. DRAFT                       PPP Compression                 October 1993
  880.  
  881.  
  882.    C.  CCP Recommended Options
  883.  
  884.       The following Configurations Options are recommended:
  885.  
  886.          IP-Compression-Protocol -- with at least 4 slots, usually 16
  887.          slots.
  888.  
  889.          IP-Address -- only on dial-up lines.
  890.  
  891.  
  892.    Security Considerations
  893.  
  894.       Security issues are not discussed in this memo.
  895.  
  896.  
  897. References
  898.  
  899.    [1]   Simpson, W. A., "The Point-to-Point Protocol", RFC in progress.
  900.  
  901.    [2]   Postel, J., "Internet Protocol", RFC 791, USC/Information
  902.          Sciences Institute, September 1981.
  903.  
  904.    [3]   Jacobson, V., "Compressing TCP/IP Headers", RFC 1144, January
  905.          1990.
  906.  
  907.    [4]   Postel, J., "The TCP Maximum Segment Size Option and Related
  908.          Topics", RFC 879, USC/Information Sciences Institute, November
  909.          1983.
  910.  
  911.    [5]   Reynolds, J., Postel,J., "Assigned Numbers", RFC 1340,
  912.          USC/Information Sciences Institute, March 1990.
  913.  
  914.    [6]   Perkins, D., Hobby, R., "Point-to-Point Protocol (PPP) initial
  915.          configuration options", RFC 1172, August 1990.
  916.  
  917.    [7]   Carr, D., "PPP Gandalf FZA Compression Protocol", Work in
  918.          progress.
  919.  
  920.    [8]   Lutz, R., "PPP Stacker LZS Compression Protocol", Work in
  921.          progress.
  922.  
  923.    [9]   Simpson, W.A., "PPP Puddle Jumper Compression Protocol", Work
  924.          in progress.
  925.  
  926.    [10]  Dimitri, T.J., "PPP Microsoft LZ Compression Protocol", Work in
  927.          progress.
  928.  
  929.  
  930.  
  931.  
  932.  
  933. Dave Rand                expires in six months                 [Page 16]
  934. DRAFT                       PPP Compression                 October 1993
  935.  
  936.  
  937. Acknowledgments
  938.  
  939.    Some of the text in this document is taken from RFCs 1171 & 1172, by
  940.    Drew Perkins of Carnegie Mellon University, and by Russ Hobby of the
  941.    University of California at Davis.
  942.  
  943.    Information leading to the expanded IP-Compression option provided by
  944.    Van Jacobson at SIGCOMM '90.
  945.  
  946.    The predictor algorithm was originally implemented by Timo Raita, at
  947.    the ACM SIG Conference, New Orleans, 1987.
  948.  
  949.    Bill Simpson helped with the document formatting.
  950.  
  951.  
  952. Chair's Address
  953.  
  954.    The working group can be contacted via the current chair:
  955.  
  956.       Fred Baker
  957.       Advanced Computer Communications
  958.       315 Bollay Drive
  959.       Santa Barbara, California 93117
  960.  
  961.       (805) 685 4455
  962.  
  963.       EMail: fbaker@acc.com
  964.  
  965.  
  966.  
  967. Author's Address
  968.  
  969.    Questions about this memo can also be directed to:
  970.  
  971.       Dave Rand
  972.       Novell, Inc.
  973.       2180 Fortune Drive
  974.       San Jose, CA  95131
  975.  
  976.       +1 408 321-1259
  977.  
  978.       EMail: dave_rand@novell.com
  979.  
  980.  
  981.  
  982.  
  983.  
  984.  
  985.  
  986.  
  987.  
  988. Dave Rand                expires in six months                 [Page 17]
  989. DRAFT                       PPP Compression                 October 1993
  990.  
  991.  
  992.                            Table of Contents
  993.  
  994.  
  995.      1.     Introduction ..........................................    1
  996.  
  997.      2.     A PPP Control Protocol (NCP) for Compression ..........    2
  998.         2.1       Sending Compressed Datagrams ....................    2
  999.  
  1000.      3.     CCP Configuration Options .............................    4
  1001.         3.1       Compression Type Negotiation Option (common) ....    5
  1002.         3.2       Compression Type Negotiation Option
  1003. (OUI/Proprietary) .................................................    7
  1004.  
  1005.      APPENDICES ...................................................    9
  1006.  
  1007.      A.     Common compression number identification ..............    9
  1008.  
  1009.      B.     Common compression algorithm definitions ..............   10
  1010.            B.1       Predictor algorithm ..........................   10
  1011.            B.2       Encapsultation for Predictor type 1 ..........   14
  1012.            B.3       Encapsultation for Predictor type 2 ..........   15
  1013.  
  1014.         C.     CCP Recommended Options ............................   16
  1015.  
  1016.         SECURITY CONSIDERATIONS ...................................   16
  1017.  
  1018.      REFERENCES ...................................................   16
  1019.  
  1020.      ACKNOWLEDGEMENTS .............................................   17
  1021.  
  1022.      CHAIR'S ADDRESS ..............................................   17
  1023.  
  1024.      AUTHOR'S ADDRESS .............................................   17
  1025.  
  1026.  
  1027.  
  1028.  
  1029.  
  1030.  
  1031.  
  1032.  
  1033.  
  1034.  
  1035.  
  1036.  
  1037.  
  1038.  
  1039.  
  1040.  
  1041.  
  1042.  
  1043.